package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.*;

public class _127_danci_jielong {
    
    static class bfs {
        
        Map<String, Integer> idMap = new HashMap<>();
        List<List<Integer>> edges = new ArrayList<>();
        int num;
        
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            for (String s : wordList) {
                addEdge(s);
            }
            addEdge(beginWord);
            if (!idMap.containsKey(endWord))
                return 0;
            int[] distances = new int[num];
            Arrays.fill(distances, -1);
            
            int beginId = idMap.get(beginWord), endId = idMap.get(endWord);
            distances[beginId] = 0;
            
            LinkedList<Integer> q = new LinkedList<>();
            q.offer(beginId);
            
            while (!q.isEmpty()) {
                int id = q.poll();
                if (id == endId)
                    return distances[id] / 2 + 1;
                for (int neighbour : edges.get(id)) {
                    if (distances[neighbour] == -1) {
                        distances[neighbour] = distances[id] + 1;
                        q.offer(neighbour);
                    }
                }
            }
            return 0;
        }
        void addEdge(String word) {
            addWord(word);
            int len = word.length();
            char[] arr = word.toCharArray();
            int id = idMap.get(word);
            for (int i = 0; i < len; i++) {
                char t = arr[i];
                arr[i] = '*';
                String newWord = new String(arr);
                addWord(newWord);
                int newId = idMap.get(newWord);
                edges.get(id).add(newId);
                edges.get(newId).add(id);
                arr[i] = t;
            }
        }
        void addWord(String word) {
            if (!idMap.containsKey(word)) {
                idMap.put(word, num++);
                edges.add(new ArrayList<>());
            }
        }
    }
    
    /**
     * 遍历的时候，如果发现当前 id 在对称方向的 dist 数组里有长度了，就可以返回了
     * */
    static class bfs_two_queue {
    
        Map<String, Integer> idMap = new HashMap<>();
        List<List<Integer>> edges = new ArrayList<>();
        int num;
    
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            for (String s : wordList) {
                addEdge(s);
            }
            addEdge(beginWord);
            if (!idMap.containsKey(endWord))
                return 0;
            int beginId = idMap.get(beginWord), endId = idMap.get(endWord);
            
            int[] distBegin = new int[num];
            Arrays.fill(distBegin, -1);
            distBegin[beginId] = 0;
            LinkedList<Integer> beginQ = new LinkedList<>();
            beginQ.offer(beginId);
    
            int[] distEnd = new int[num];
            Arrays.fill(distEnd, -1);
            distEnd[endId] = 0;
            LinkedList<Integer> endQ = new LinkedList<>();
            endQ.offer(endId);
            
            while (!beginQ.isEmpty() && !endQ.isEmpty()) {
                int size1 = beginQ.size();
                for (int i = 0; i < size1; i++) {
                    int id1 = beginQ.poll();
                    if (distEnd[id1] != -1)
                        return (distBegin[id1] + distEnd[id1]) / 2 + 1;
                    for (int neighbour : edges.get(id1)) {
                        if (distBegin[neighbour] == -1) {
                            distBegin[neighbour] = distBegin[id1] + 1;
                            beginQ.offer(neighbour);
                        }
                    }
                }
    
                int size2 = endQ.size();
                for (int i = 0; i < size2; i++) {
                    int id2 = endQ.poll();
                    if (distBegin[id2] != -1)
                        return (distBegin[id2] + distEnd[id2]) / 2 + 1;
                    for (int neighbour : edges.get(id2)) {
                        if (distEnd[neighbour] == -1) {
                            distEnd[neighbour] = distEnd[id2] + 1;
                            endQ.offer(neighbour);
                        }
                    }
                }
            }
            return 0;
        }
        void addEdge(String word) {
            addWord(word);
            int len = word.length();
            char[] arr = word.toCharArray();
            int id = idMap.get(word);
            for (int i = 0; i < len; i++) {
                char t = arr[i];
                arr[i] = '*';
                String newWord = new String(arr);
                addWord(newWord);
                int newId = idMap.get(newWord);
                edges.get(id).add(newId);
                edges.get(newId).add(id);
                arr[i] = t;
            }
        }
        void addWord(String word) {
            if (!idMap.containsKey(word)) {
                idMap.put(word, num++);
                edges.add(new ArrayList<>());
            }
        }
    }
    
}
